package solutions.leetcode.normal;

import solutions.lib.BaseSolution;
import solutions.lib.TreeNode;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/maximum-binary-tree/">654. 最大二叉树</a>
 */
public class Solution654 extends BaseSolution {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        // 根据题意， 1001 为不可逾越的最大值
        TreeNode node = new TreeNode(1001);
        init(nums, node, 0);
        return node.right;
    }

    private int init(int[] nums, TreeNode parent, int ind) {
        while (ind >= 0 && ind < nums.length) {
            if (nums[ind] < parent.val) {
                TreeNode now = new TreeNode(nums[ind]);
                // region 如果当前结点有 right，说明是回溯来的，把右节点做为新节点的左子节点
                TreeNode tmp = parent.right;
                parent.right = now;
                now.left = tmp;
                // endregion
                ind = init(nums, now, ind + 1);
            } else {
                return ind;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Solution654 solution = new Solution654();
    }
}